package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2022/1/27.<br><br>
 *
 * 中等：二叉搜索树中第K小的元素
 */
public class Topic230 {

    public static void main(String[] args) {
        BaseSolution solution = new Solution2();

        TreeNode root = Util.createTree(Arrays.asList(3,1,4,null,2));
        System.out.println(solution.kthSmallest(root, 1));

        root = Util.createTree(Arrays.asList(5,3,6,2,4,null,null,1));
        System.out.println(solution.kthSmallest(root, 3));
    }

    private interface BaseSolution {
        int kthSmallest(TreeNode root, int k);
    }

    private static class Solution1 implements BaseSolution {

        private int counter = 0;

        @Override
        public int kthSmallest(TreeNode root, int k) {
            counter = 0;
            return helper(root, k);
        }

        private int helper(TreeNode root, int k) {
            if(root == null) {
                return -1;
            }

            int left = helper(root.left, k);

            if(++counter == k) {
                return root.val;
            }

            int right = helper(root.right, k);

            return left == -1 ? right : left;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public int kthSmallest(TreeNode root, int k) {
            return helper(root, k);
        }

        private int helper(TreeNode root, int k) {
            Deque<TreeNode> stack = new LinkedList<>();

            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }

                root = stack.pop();
                if(--k == 0) {
                    return root.val;
                }

                root = root.right;
            }

            return -1;
        }
    }
}
